package org.ala.linshen.dp;

import java.util.Arrays;

/**
 * 给你一个 rows x cols 的矩阵 grid 来表示一块樱桃地。 grid 中每个格子的数字表示你能获得的樱桃数目。
 *
 * 你有两个机器人帮你收集樱桃，机器人 1 从左上角格子 (0,0) 出发，机器人 2 从右上角格子 (0, cols-1) 出发。
 *
 * 请你按照如下规则，返回两个机器人能收集的最多樱桃数目：
 *
 * 从格子 (i,j) 出发，机器人可以移动到格子 (i+1, j-1)，(i+1, j) 或者 (i+1, j+1) 。
 * 当一个机器人经过某个格子时，它会把该格子内所有的樱桃都摘走，然后这个位置会变成空格子，即没有樱桃的格子。
 * 当两个机器人同时到达同一个格子时，它们中只有一个可以摘到樱桃。
 * 两个机器人在任意时刻都不能移动到 grid 外面。
 * 两个机器人最后都要到达 grid 最底下一行。
 *
 *
 * 示例 1：
 *
 *
 *
 * 输入：grid = [[3,1,1],[2,5,1],[1,5,5],[2,1,1]]
 * 输出：24
 * 解释：机器人 1 和机器人 2 的路径在上图中分别用绿色和蓝色表示。
 * 机器人 1 摘的樱桃数目为 (3 + 2 + 5 + 2) = 12 。
 * 机器人 2 摘的樱桃数目为 (1 + 5 + 5 + 1) = 12 。
 * 樱桃总数为： 12 + 12 = 24 。
 * 示例 2：
 *
 * 输入：grid = [[1,0,0,0,0,0,1],[2,0,0,0,0,3,0],[2,0,9,0,0,0,0],[0,3,0,5,4,0,0],[1,0,2,3,0,0,6]]
 * 输出：28
 * 解释：机器人 1 和机器人 2 的路径在上图中分别用绿色和蓝色表示。
 * 机器人 1 摘的樱桃数目为 (1 + 9 + 5 + 2) = 17 。
 * 机器人 2 摘的樱桃数目为 (1 + 3 + 4 + 3) = 11 。
 * 樱桃总数为： 17 + 11 = 28 。
 * 示例 3：
 *
 * 输入：grid = [[1,0,0,3],[0,0,0,3],[0,0,3,3],[9,0,3,3]]
 * 输出：22
 * 示例 4：
 *
 * 输入：grid = [[1,1],[1,1]]
 * 输出：4
 *
 *
 * 提示：
 *
 * rows == grid.length
 * cols == grid[i].length
 * 2 <= rows, cols <= 70
 * 0 <= grid[i][j] <= 100
 *
 * @author ala
 * @date 2024-09-27 12:14
 */
public class Q1463 {

    public static void main(String[] args) {
        Q1463 q = new Q1463();

//        int[][] grid = {{3,1,1},{2,5,1},{1,5,5},{2,1,1}};
//        int[][] grid = {{1,0,0,0,0,0,1},{2,0,0,0,0,3,0},{2,0,9,0,0,0,0},{0,3,0,5,4,0,0},{1,0,2,3,0,0,6}};
//        int[][] grid = {{1,0,0,3},{0,0,0,3},{0,0,3,3},{9,0,3,3}};
        int[][] grid = {{9,0,1,4,4,5},{0,6,1,10,2,4},{6,8,7,1,9,3},{2,10,9,7,6,9},{9,4,9,2,3,0},{3,6,2,3,8,4},{4,10,5,0,6,7},{8,1,7,3,7,0}};

        System.out.println(q.cherryPickup(grid));
    }

    public int cherryPickup(int[][] grid) {
        return V1(grid);
    }
    static int INF = Integer.MIN_VALUE >> 1;
    /**
     *  1）dp[i][j1][j2]表示：在第i行，第一个人在j1，第二个人在j2，能摘的最大樱桃数
     *  2）dp[0][0][N-1] = grid[0][0] + grid[0][N - 1]，其他都是 INF
     *  3）dp[i][j1][j2] = max(
     *                      dp[i-1][j1-1][j2]
     *                      dp[i-1][j1][j2]
     *                      dp[i-1][j1+1][j2]
     *
     *                      dp[i-1][j1-1][j2-1]
     *                      dp[i-1][j1][j2-1]
     *                      dp[i-1][j1+1][j2-1]
     *
     *                      dp[i-1][j1-1][j2+1]
     *                      dp[i-1][j1][j2+1]
     *                      dp[i-1][j1+1][j2+1]
     *                      ) + grid[i][j1] + grid[i][j2]
     *                      当 j1 == j2 时，grid[i][j2] = 0
     *  4）最后一层取最大值就是答案
     */
    protected int V1(int[][] grid) {
        int M = grid.length, N = grid[0].length;

        int[][][] dp = new int[M][N][N];
        for (int j1 = 0 ; j1 < N ; j1++) {
            for (int j2 = 0 ; j2 < N ; j2++) {
                dp[0][j1][j2] = INF;
            }
        }
        dp[0][0][N - 1] = grid[0][0] + grid[0][N - 1];

        StringBuilder sbuf = new StringBuilder("[");
        for (int[] arr : dp[0]) {
            sbuf.append(Arrays.toString(arr));
        }
        sbuf.append("]");
        System.out.println(sbuf);


        int res = 0;
        for (int i = 1 ; i < M ; i++) {
            for (int j1 = 0 ; j1 < N ; j1++) {
                for (int j2 = 0 ; j2 < N ; j2++) {
                    //  j2 - 1 的 3中路径
                    int v1 = INF;
                    if (j2 > 0) {
                        v1 = dp[i - 1][j1][j2 - 1];
                        int v11 = j1 > 0 ? dp[i - 1][j1 - 1][j2 - 1] : INF,
                            v12 = j1 < N - 1 ? dp[i - 1][j1 + 1][j2 - 1] : INF;
                        v1 = Math.max(v1, Math.max(v11, v12));
                    }
                    //  j2 的 3种路径
                    int v2 = dp[i - 1][j1][j2];
                    int v21 = j1 > 0 ? dp[i - 1][j1 - 1][j2] : INF,
                        v22 = j1 < N - 1 ? dp[i - 1][j1 + 1][j2] : INF;
                    v2 = Math.max(v2, Math.max(v21, v22));
                    //  j2 + 1 的3种路径
                    int v3 = INF;
                    if (j2 < N - 1) {
                        v3 = dp[i - 1][j1][j2 + 1];
                        int v31 = j1 > 0 ? dp[i - 1][j1 - 1][j2 + 1] : INF,
                            v32 = j1 < N - 1 ? dp[i - 1][j1 + 1][j2 + 1] : INF;
                        v3 = Math.max(v3, Math.max(v31, v32));
                    }

                    int g1 = grid[i][j1], g2 = grid[i][j2];
                    if (j1 == j2) {
                        g2 = 0;
                    }
                    dp[i][j1][j2] = Math.max(v1, Math.max(v2, v3)) + g1 + g2;
                    if (i == M - 1) {
                        res = Math.max(res, dp[i][j1][j2]);
                    }
                }
            }
            sbuf = new StringBuilder("[");
            for (int[] arr : dp[i]) {
                sbuf.append(Arrays.toString(arr));
            }
            sbuf.append("]");
            System.out.println(sbuf);
        }
        return res;
    }
}
